package com.learn.algorithm;

public class Search {

    /**
     * 在有序数组中查找一个数 找到返回true 否则返回false
     */
    public static boolean search(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] < target) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return false;
    }

    /**
     * 在有序数组中找到大于等于target的最左侧的位置
     */
    public static int mostLeft(int[] arr, int target) {
        int answer = -1;
        if (arr == null || arr.length == 0) {
            return answer;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (arr[mid] >= target) {
                answer = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return answer;
    }

    /**
     * 在一个相邻元素不相等的数组中找到其中的一个峰值的位置
     * 峰值: 该元素比其左右相邻元素都大
     * 1. 边界条件检查
     * 2. 检查 0 和 N-1位置是否为峰值
     * 3. 1..N-2位置上判断
     * 中点是峰值则返回
     * 中点不是峰值: 左边大于中点 峰值出现在左边
     * 右边大于中点 峰值出现在右边
     */
    public static int localPeak(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        if (arr[0] > arr[1]) {
            return 0;
        }
        if (arr[N - 2] < arr[N - 1]) {
            return N - 1;
        }
        int L = 1;
        int R = N - 2;
        int ans = -1;
        int m = 0;
        while (L <= R) {
            m = L + (R - L) / 2;
            if (arr[m - 1] > arr[m]) {
                R = m - 1;
            } else if (arr[m] < arr[m + 1]) {
                L = m + 1;
            } else {
                ans = m;
                break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 7, 8, 9};
        System.out.println(search(arr, 0));
        System.out.println(search(arr, 1));
        System.out.println(search(arr, 4));
        System.out.println(search(arr, 5));
        System.out.println(search(arr, 9));
        System.out.println(search(arr, 10));

        System.out.println(mostLeft(arr, 0));
        System.out.println(mostLeft(arr, 1));
        System.out.println(mostLeft(arr, 10));
        System.out.println(mostLeft(arr, 11));

        System.out.println(localPeak(new int[]{2, 1}));
    }
}
